package leetcode;

import java.util.Arrays;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class LowestCommonAncestor {

	public static void main(String[] args) {
		int[] pre = {3, 8, 5, 7, 4, 9, 10, 1};
		int[] in = {5, 7, 8, 4, 3, 10, 1, 9};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		LowestCommonAncestor object = new LowestCommonAncestor();
		TreeNode p = root.left.left;
		TreeNode q = root.left.right;
		System.out.println("p val: " + p.val + " q val: " + q.val);
		TreeNode lca = object.lowestCommonAncestor(root, p, q);
		System.out.println(lca.val);
	}
	
	//自底向上的实现用一句话来总结就是——如果遍历到的当前节点是 A/B 中的任意一个，那么我们就向父节点汇报此节点，
	//否则递归到节点为空时返回空值。具体来说会有如下几种情况：

	// 当前节点不是两个节点中的任意一个，此时应判断左右子树的返回结果。
	// 若左右子树均返回非空节点，那么当前节点一定是所求的根节点，将当前节点逐层向前汇报。	// 两个节点分居树的两侧
	// 若左右子树仅有一个子树返回非空节点，则将此非空节点向父节点汇报。	// 节点仅存在于树的一侧
	// 若左右子树均返回NULL, 则向父节点返回NULL.	// 节点不在这棵树中
	
	// 当前节点即为两个节点中的一个，此时向父节点返回当前节点。
	// 根据此递归模型容易看出应该使用中序遍历来实现。
	
	//12ms, beat 45.82%, and 40% is 12ms
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (p == null) {
			return q;
		}
		if (q == null) {
			return p;
		}
		// return either p or q or null
		if (root == null || p == root || q == root) {
			return root;
		}
		TreeNode left = lowestCommonAncestor(root.left, p, q);
		TreeNode right = lowestCommonAncestor(root.right, p, q);
		
		if (left == null && right == null) {
			//如果都没有找到，像父节点返回false
			return null;
		} else 
			//分别在左子树和右子树
			if (left != null && right != null) {
			return root;
		} else {
			// either left or right or NULL
			return left == null ? right : left;
		}
	}
	
	// 1093ms， beat 0.01%
	public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
		if (p == null) {
			return q;
		}
		if (q == null) {
			return p;
		}
		if (root == null) {
			return null;
		}
		if (p == root || q == root) {
			return root;
		}
		boolean pIsLeft = covers(root.left, p);
		boolean qIsLeft = covers(root.left, q);
		if (pIsLeft && qIsLeft) {
			return lowestCommonAncestor(root.left, p, q);
		} else if (!pIsLeft && !qIsLeft) {
			return lowestCommonAncestor(root.right, p, q);
		} else {
			return root;
		}
	}

	// 首先仿造BST的思路逐步的判断是否在左子树上或者在右子树上
	private boolean covers(TreeNode rootNode, TreeNode n) {
		if (rootNode == null)
			return false;
		if (rootNode == n)
			return true;
		return covers(rootNode.left, n) || covers(rootNode.right, n);
	}
}
